﻿import math

#二分查找算法
def binary_search(a, e):
    low = 0
    high = len(a)-1
    
    while low != high:
        mid = float(low + high)/2
        mid1 = int(math.floor(mid))
        mid2 = int(math.ceil(mid))
        center = float(a[mid1]+a[mid2])/2
        
        if e < center:
            high = mid1
        elif e > center:
            low = mid2
        else:
            break;
    if e>=a[low]:
        return low+1
    else:
        return low

#二分插入排序算法
def mod_insert_sort(a):
    for i in range(1, len(a)):
        pos = binary_search(a[0:i], a[i])
        a_i = a[i]
        for k in range(pos, i)[::-1]:
            a[k+1] = a[k]
        a[pos] = a_i
